﻿'use strict';

// Bypass node.js limitation on abrut exit bypassing some output to
// stdout when redirecting the output in a pipe.
//
// As of today (2014-03-06) when node.js detects stdout is plugged to
// a pipe it writes to it asynchronously (from the event loop). But if
// an abrut exit happen (for example if an uncaught exception is
// raised) these pending writting won't be flushed before the
// exception's stack is written and the process terminated. That means
// that the output is lost; which can be really annoying when
// debugging a script.
//
// The bypass is to add an 'uncaughtException' event handler that log
// the exception using console.log and set the return code of the
// process to a global variable. This variable is then read in an
// 'exit' event handler when the process actually exits after the
// termination of the event loop (which is triggered by the uncaught
// exception). In this event handler we can then call process.exit
// without having to fear losing traces.
var process_returncode = 0;

/**
 * Install the bypass.
 *
 * <p>Must be called once at start of the program.</p>
 */
function installExitBypass() {
    process.on('uncaughtException', function (err) {
        if (err.stack) {
            console.log(err.stack);
        } else {
            console.log("Stackless uncaught exception: " + err);
        }
        process_returncode = 2;
    });

    process.on('exit', function () {
        if (process_returncode) {
            process.exit(process_returncode);
        }
    });
}

/**
 * @typedef {object} ProbabilityDistrib~Item
 *
 * @property {*} key the key returned for this item by the probability
 * distribution
 *
 * @property {number} p the probability for this item
 */

/**
 * Discreet distrubition of probabilities in a collection.
 *
 * <p>This object transforms a uniform random source in [0,1) to a
 * random choice of items each having an associated probability.</p>
 *
 * <p>For example:
 * @code
 * var d = new ProbabilityDistrib([{ key: 'a', p: 0.25 }, { key: 'b', p: 0.75 }]);
 * var x = d.getKey(Math.random());
 * @endcode
 * then:
 *   - <tt>Pr(x='a') = 0.25</tt>
 *   - <tt>Pr(x='b') = 0.75</tt>
 * (assuming <tt>Math.random()</tt> is uniform).</p>
 *
 * <p>If the sum of the wanted probabilities of items is not 1 the
 * probabilities are normalized by this constructor.</p>
 *
 * @constructor
 * @param {Array<ProbabilityDistrib~Item>} items
 */
function ProbabilityDistrib(items)
{
    var sum, i, n, p;

    n = items.length;
    if (!n) { throw new Error("items is empty"); }

    // compute probability sum
    sum = 0;
    for (i = 0; i < n; ++i) {
        if (!isNaN(items[i].p) && items[i].p >= 0) {
            sum += items[i].p;
        }
    }

    if (!isFinite(sum)) { throw new Error("items have invalid probabilities"); }

    // build the two arrays of cumulated probabilities and keys
    this.cumulated = new Array(n - 1);
    this.keys = new Array(n);
    for (i = 0; i < n - 1; ++i) {
        p = items[i].p;
        if (isNaN(p) || p < 0) { p = 0; }

        this.cumulated[i] = i ? this.cumulated[i-1] : 0;
        this.cumulated[i] += p / sum;
    }
    for (i = 0; i < n; ++i) {
        this.keys[i] = items[i].key;
    }
}

/**
 * Get the key corresponding to given value in [0;1) range.
 *
 * @param {number} nb expect 0 <= nb < 1 (no check is made)
 * @return {*} the key of the picked element
 */
ProbabilityDistrib.prototype.getKey = function (nb) {
    var i, j, m;

    // do a binary search
    i = 0, j = this.cumulated.length;

    while (i < j) {
        // invariant : ∀ x < i : cumulated[x] <= nb
        //             ∀ x => j: cumulated[x] >  nb
        m = i + ((j - i) >>> 1);

        if (this.cumulated[m] <= nb) {
            i = m + 1;
        } else {
            j = m;
        }
    }
    // termination : 0 <= i == j <= this.cumulated.length
    //               ∀ x < i : cumulated[x] <= nb
    //               ∀ x => i: cumulated[x] >  nb
    // note this.keys.length = this.cumulated.length + 1 so i is always valid
    return this.keys[i];
};


/**
 * @param {*} [opts] an object used to retrieve options or <tt>null|undefined</tt>
 *
 * @param {string} key the key to use to find the value in <tt>opts</tt>
 *
 * @param {*} defValue the default value to returns if <tt>opts</tt>
 * is <tt>null|undefined</tt> or if its <tt>key</tt> property is
 * undefined
 *
 * @return {*} the attribute <tt>key</tt> of <tt>opts</tt> object if
 * <tt>opts</tt> is not <tt>null|undefined</tt> and it has an
 * attribute <tt>key</tt> whose value is not <tt>undefined</tt>; else returns <tt>defValue</tt>
 */
function getOpt(opts, key, defValue) {
    return opts && opts[key] !== undefined ? opts[key] : defValue;
}

/**
 * Wrapper of @ref getOpt for <tt>boolean</tt> values.
 *
 * <p>It makes sure the returned value is always a <tt>boolean</tt>.</p>
 *
 * @return {boolean} the value
 */
function getBoolOpt(opts, key, defValue) {
    return Boolean(getOpt(opts, key, defValue));
}

/**
 * Wrapper of @ref getOpt for <tt>number</tt> values.
 *
 * <p>It makes sure the returned value is always a <tt>number</tt>.</p>
 *
 * @return {number} the value
 */
function getNumberOpt(opts, key, defValue) {
    return Number(getOpt(opts, key, defValue));
}

/**
 * @constructor
 *
 * <p>Example:
 * @code
 * var g = new RandomGenerator({ 'ws': true });
 * var jsonText = g.generateText();
 * @endcode
 * </p>
 */
function RandomGenerator(opts) {
    this.strict              = getBoolOpt(opts, 'strict', false);
    this.pretty              = getBoolOpt(opts, 'pretty', false);
    this.ws                  = getBoolOpt(opts, 'ws', false);
    this.ws_max              = getBoolOpt(opts, 'ws_max', 3);

    this.str_max             = getNumberOpt(opts, 'str_max', 6);
    this.p_str_regular       = getNumberOpt(opts, 'p_str_regular', 0.95);
    this.p_str_regular_ascii = getNumberOpt(opts, 'p_str_regular_ascii', 0.95);
    this.p_str_uesc_upcase   = getNumberOpt(opts, 'p_str_uesc_upcase', 0.5);

    this.p_nb_negative       = getNumberOpt(opts, 'p_nb_negative', 0.5);
    this.p_nb_int_zero       = getNumberOpt(opts, 'p_nb_int_zero', 0.3);
    this.p_nb_frac           = getNumberOpt(opts, 'p_nb_frac', 0.5);
    this.p_nb_exp            = getNumberOpt(opts, 'p_nb_exp', 0.2);
    this.p_nb_exp_negative   = getNumberOpt(opts, 'p_nb_exp_negative', 0.5);
    this.p_nb_exp_pos_sgn    = getNumberOpt(opts, 'p_nb_exp_pos_sgn', 0.25);
    this.nb_max_int          = getNumberOpt(opts, 'nb_max_int', 1000);
    this.nb_max_frac_digits  = getNumberOpt(opts, 'nb_max_frac_digits', 6);
    this.nb_max_exp_digits   = getNumberOpt(opts, 'nb_max_exp_digits', 3);


    this.p_array_vs_object   = getNumberOpt(opts, 'p_array_vs_object', 0.5);
    this.children_max        = getNumberOpt(opts, 'children_max', 5);
    this.duplicate_keys      = getBoolOpt(opts, 'duplicate_keys', false);

    this.p_value_object      = getNumberOpt(opts, 'p_value_object'   , 0.2);
    this.p_value_array       = getNumberOpt(opts, 'p_value_array'    , 0.2);
    this.p_value_boolean     = getNumberOpt(opts, 'p_value_boolean'  , 0.15);
    this.p_value_null        = getNumberOpt(opts, 'p_value_null'     , 0.05);
    this.p_value_number      = getNumberOpt(opts, 'p_value_number'   , 0.2);
    this.p_value_string      = getNumberOpt(opts, 'p_value_string'   , 0.2);

    this.p_ws_space          = getNumberOpt(opts, 'p_ws_space', 0.7);
    this.p_ws_hztab          = getNumberOpt(opts, 'p_ws_hztab', 0.1);
    this.p_ws_lf             = getNumberOpt(opts, 'p_ws_lf', 0.1);
    this.p_ws_cr             = getNumberOpt(opts, 'p_ws_cr', 0.1);

    this.max_recursion       = getNumberOpt(opts, 'max_recursion'  , 3);

    // probability distrubition for value type, assuming we can pick
    // objects/arrays (recursion <= this.max_recursion)
    this.pd_all_values = new ProbabilityDistrib([
        { key: RandomGenerator.t_object , p: this.p_value_object },
        { key: RandomGenerator.t_array  , p: this.p_value_array },
        { key: RandomGenerator.t_boolean, p: this.p_value_boolean },
        { key: RandomGenerator.t_null   , p: this.p_value_null },
        { key: RandomGenerator.t_number , p: this.p_value_number },
        { key: RandomGenerator.t_string , p: this.p_value_string },
    ]);

    // probability distrubition for value type, assuming we can't pick
    // objects/arrays (recursion > this.max_recursion)
    this.pd_nonrec_values = new ProbabilityDistrib([
        { key: RandomGenerator.t_boolean, p: this.p_value_boolean },
        { key: RandomGenerator.t_null   , p: this.p_value_null },
        { key: RandomGenerator.t_number , p: this.p_value_number },
        { key: RandomGenerator.t_string , p: this.p_value_string },
    ]);

    // probability distrubition for types of whitespaces
    this.pd_ws = new ProbabilityDistrib([
        { key: ' ',  p: this.p_ws_space },
        { key: '\t', p: this.p_ws_hztab },
        { key: '\n', p: this.p_ws_lf    },
        { key: '\r', p: this.p_ws_cr    }
    ]);

    // probability distrubition for numbers' exponent sign
    this.pd_exp_sgn = new ProbabilityDistrib([
        { key: '-', p: this.p_nb_exp_negative },
        { key: '+', p: this.p_nb_exp_pos_sgn },
        { key: '',  p: 1-(this.p_nb_exp_pos_sgn + this.p_nb_exp_negative) }
    ]);
}

/**
 * Generate a JSON document.
 *
 * If 'strict' option is set only returns an array or an object; else
 * returns any value (object, array, true, false, null, string,
 * number).
 */
RandomGenerator.prototype.generateText = function () {
    var indent;

    if (this.pretty) {
        indent = '';
    }

    if (this.strict) {
        if (Math.random() >= this.p_array_vs_object) {
            return this.generateWS() + this.generateArray(0, indent) + this.generateWS();
        } else {
            return this.generateWS() + this.generateObject(0, indent) + this.generateWS();
        }
    } else {
        return this.generateWS() + this.generateValue(0, indent) + this.generateWS();
    }
};

RandomGenerator.prototype.generateWS = function () {
    var out, n;
    out = [];
    if (this.ws && ! this.pretty) {
        for (n = (Math.random() * (this.ws_max + 1)) | 0; n; --n) {
            out.push(this.pd_ws.getKey(Math.random()));
        }
    }
    return out.join('');
};

RandomGenerator.prototype.generateValue = function (rec, indent) {
    var pt;

    // select the probability table corresponding to all values of
    // only non recursive (i.e. not object/array) ones
    pt = rec === this.max_recursion ? this.pd_nonrec_values : this.pd_all_values;

    return RandomGenerator.generateFunctions[pt.getKey(Math.random())].call(this, rec, indent);
};

RandomGenerator.prototype.generateObject = function (rec, indent) {
    var n, out, first, childIndent, key, keys, limit;

    limit = 500;
    keys = {};
    out = [];
    out.push([ '{' ]);
    out.push(this.generateWS());
    first = true;

    if (this.pretty) {
        childIndent = indent + '  ';
    }

    for (n = (Math.random() * (this.children_max + 1)) | 0; n; --n) {
        if (first) {
            first = false;
        } else {
            out.push(',');
        }
        if (this.pretty) { out.push('\n'); out.push(childIndent); }
        do {
            key = this.generateString();
            --limit;
        } while (!this.duplicate_keys && keys.hasOwnProperty(key) && limit >= 0);
        if (limit < 0) { throw new Error('failed to generate not duplicated keys after 500 tries'); }
        keys[key] = true;
        out.push(key);
        out.push(this.generateWS());
        out.push(':');
        out.push(this.generateWS());
        out.push(this.generateValue(rec + 1, childIndent));
    }
    if (this.pretty && !first) { out.push('\n'); out.push(indent); }
    out.push(this.generateWS());
    out.push('}');

    return out.join('');
};

RandomGenerator.prototype.generateArray = function (rec, indent) {
    var n, out, first, childIndent;

    out = [];
    out.push(this.generateWS());
    out.push('[');
    out.push(this.generateWS());
    first = true;

    if (this.pretty) {
        childIndent = indent + '  ';
    }

    for (n = (Math.random() * (this.children_max + 1)) | 0; n; --n) {
        if (first) {
            first = false;
        } else {
            out.push(',');
        }
        if (this.pretty) { out.push('\n'); out.push(childIndent); }
        out.push(this.generateValue(rec + 1, childIndent));
        out.push(this.generateWS());
    }
    if (this.pretty && !first) { out.push('\n'); out.push(indent); }
    out.push(this.generateWS());
    out.push(']');

    return out.join('');
};

RandomGenerator.prototype.generateBoolean = function () {
    return Math.random() < 0.5 ? "true" : "false";
};

RandomGenerator.prototype.generateNull = function () {
    return "null";
};

RandomGenerator.prototype.generateNumber = function () {
    var out, n, r;

    out = '';

    // add the sign
    if (Math.random() < this.p_nb_negative) {
        out += '-';
    }

    // add the integer part '0' | '1'..'9' '0'..'9'*
    if (Math.random() < this.p_nb_int_zero) {
        out += '0';
    } else {
        out += String(Math.random() * this.nb_max_int + 1 | 0);
    }

    // add optional fractional part
    if (Math.random() < this.p_nb_frac) {
        out += '.';
        for (n = Math.random() * this.nb_max_frac_digits + 1 | 0; n; --n) {
            out += String(Math.random() * 10 | 0);
        }
    }

    // add optional exponential part
    if (Math.random() < this.p_nb_exp) {
        out += 'e';
        out += this.pd_exp_sgn.getKey(Math.random());
        for (n = Math.random() * this.nb_max_exp_digits + 1 | 0; n; --n) {
            out += String(Math.random() * 10 | 0);
        }
    }

    return out;
};

RandomGenerator.escapes = [ '"', '\\', '/', 'b', 'f', 'n', 'r', 't', 'u' ];
RandomGenerator.hexdigits = [ '0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'a', 'b', 'c', 'd', 'e', 'f' ];

RandomGenerator.prototype.generateString = function () {
    var out, n, c, max, that;

    function to4HexString(n) {
        var i, r, d;
        r = '';
        for (i = 4; i-- > 0;) {
            d = RandomGenerator.hexdigits[(n >>> (i << 2)) & 0xf];
            if (Math.random() < that.p_str_uesc_upcase) {
                d = d.toUpperCase();
            }
            r += d;
        }
        return r;
    }

    that = this;

    out = [];
    out.push('"');

    for (n = (Math.random() * (this.str_max + 1)) | 0; n; --n) {
        // find the type of character to insert
        if (Math.random() < this.p_str_regular) {
            // regular character
            do {
                // pick ascii characters
                if (Math.random() < this.p_str_regular_ascii) {
                    c = (0x20 + Math.random() * (0x7f - 0x20)) | 0;
                } else {
                    c = (0x7f + Math.random() * (1 + 0x10FFFF - 0x7f)) | 0;
                }
            } while (c == 0x22 || c == 0x5c || (c >= 0xd800 && c <= 0xdfff));
            if (c > 0xFFFF) {
                c -= 0x010000;
                out.push(String.fromCharCode(0xD800 + (c >>> 10), 0xDC00 + (c & 0x3ff)));
            } else {
                out.push(String.fromCharCode(c));
            }
        } else {
            // escape character
            c = RandomGenerator.escapes[(Math.random() * RandomGenerator.escapes.length) | 0];
            out.push('\\', c);
            if (c === 'u') {
                max = n > 1 ? 0x10FFFF : 0xFFFF;
                do {
                    c = (Math.random() * (1 + max)) | 0;
                } while (c == 0x22 || c == 0x5c || (c >= 0xd800 && c <= 0xdfff));
                if (c > 0xFFFF) {
                    c -= 0x010000;
                    out.push(to4HexString(0xD800 + (c >>> 10)));
                    out.push('\\u');
                    out.push(to4HexString(0xDC00 + (c & 0x3ff)));
                    --n;
                } else {
                    out.push(to4HexString(c));
                }
            }
        }
    }

    out.push('"');

    return out.join('');
};

// enumaration of types for values
RandomGenerator.t_object = 0;
RandomGenerator.t_array = 1;
RandomGenerator.t_boolean = 2;
RandomGenerator.t_null = 3;
RandomGenerator.t_number = 4;
RandomGenerator.t_string = 5;

// an array that is used as a map from type of values to their
// corresponding generation function
RandomGenerator.generateFunctions = [];
RandomGenerator.generateFunctions[RandomGenerator.t_object]  = RandomGenerator.prototype.generateObject;
RandomGenerator.generateFunctions[RandomGenerator.t_array]   = RandomGenerator.prototype.generateArray;
RandomGenerator.generateFunctions[RandomGenerator.t_boolean] = RandomGenerator.prototype.generateBoolean;
RandomGenerator.generateFunctions[RandomGenerator.t_null]    = RandomGenerator.prototype.generateNull;
RandomGenerator.generateFunctions[RandomGenerator.t_number]  = RandomGenerator.prototype.generateNumber;
RandomGenerator.generateFunctions[RandomGenerator.t_string]  = RandomGenerator.prototype.generateString;

// a live test of ProbabilityDistrib objects; a test is ok when the
// line starts with a '_' and KO when it starts with a '!'
//
// FIXME: move that to a test file
function testProbabilityDistrib() {
    function tests(id, p) {
        function t(x, expected) {
            var out;
            out = p.getKey(x);
            if (out === expected) {
                console.log('_ p.getKey(' + x + ') = ' + out);
            } else {
                console.log('! p.getKey(' + x + ') = ' + out + ' instead of ' + expected);
            }
        }

        console.log('test ' + id + ':');
        console.log('cumulated: ' + p.cumulated);
        console.log('keys:      ' + p.keys);
        t(-Infinity, 'a');
        t(-0.5, 'a');
        t(0, 'a');
        t(0.1, 'a');
        t(0.25, 'b');
        t(0.3, 'b');
        t(0.375, 'c');
        t(0.5, 'c');
        t(0.875, 'd');
        t(0.9, 'd');
        t(1.0, 'd');
        t(1.5, 'd');
        t(Infinity, 'd');
        console.log('');
    }

    tests("sum = 1", new ProbabilityDistrib([
        { key: "a" , p: 0.25 },
        { key: "b" , p: 0.125 },
        { key: "b2", p: 0 },
        { key: "b3", p: 0 },
        { key: "c" , p: 0.5 },
        { key: "d" , p: 0.125 }
    ]));
    tests("sum = 1000", new ProbabilityDistrib([
        { key: "a" , p: 250 },
        { key: "b" , p: 125 },
        { key: "b2", p: 0 },
        { key: "b3", p: 0 },
        { key: "c" , p: 500 },
        { key: "d" , p: 125 }
    ]));
    tests("sum negative prob", new ProbabilityDistrib([
        { key: "a" , p: 250 },
        { key: "b" , p: 125 },
        { key: "b2", p: -15 },
        { key: "b3", p: 0 },
        { key: "c" , p: 500 },
        { key: "d" , p: 125 }
    ]));


}

// Test the random generator
//
// FIXME: do a proper parsing of command line options (and reading of
// FIXME: option file) and make a usable program
function testRandomGenerator() {
    var g, json;

    function quoteCR(s) {
        return s.replace(/\r/g, '<cr>');
    }

    g = new RandomGenerator({ strict: true, /*pretty: true,*/ ws: true });

    json = g.generateText();
    console.log(quoteCR(json));
    console.log(JSON.parse(json));
}

function main() {
    installExitBypass();
    //testProbabilityDistrib();
    testRandomGenerator();
}

// Start main() only when not used as a module
if (require.main === module) {
    main();
}

// node.js module's exported symbols
exports.ProbabilityDistrib = ProbabilityDistrib;
exports.RandomGenerator = RandomGenerator;
